package club.vann.nowcoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * <p>难度：Medium</p>
 * <p>题目：数组中相加和为0的三元组</p>
 * <p>描述：给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
 * 注意：
 * 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
 * 解集中不能包含重复的三元组。
 * 例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)
 *
 * 示例1
 * 输入
 * 复制
 * [-2,0,1,1,2]
 * 返回值
 * 复制
 * [[-2,0,2],[-2,1,1]]</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-22:09:34:52
 */
public class NC54 {
    public static void main(String[] args) {
        NC54 nc54 = new NC54();

        ArrayList<ArrayList<Integer>> ans = null;
        ans = nc54.threeSum1(TestCase.NUM);
        System.out.println("Success");
    }

    /**
     * 解法一：
     * 暴力破解，超时。
     *
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int n = num.length;
        if(n < 3) {
            return ans;
        }

        Arrays.sort(num);
        for(int i = 0; i < n-2; i ++) {
            for(int j = i+1; j < n-1; j ++) {
                for(int t = j+1; t < n; t ++) {
                    if(num[i]+num[j]+num[t] == 0) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[t]);
                        ans.add(list);
                    }
                }
            }
        }

        return ans;
    }

    /**
     * 解法二：
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum1(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int n = num.length;
        if(n < 3) {
            return ans;
        }

        Arrays.sort(num);

        for(int i = 0; i < n-2; i ++) {
            int a = num[i];
            int j = i+1;
            int t = n-1;
            int target = -a;
            while(j < t) {
                if(num[j] + num[t] > target) {
                    t --;
                } else if(num[j] + num[t] < target) {
                    j ++;
                } else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[j]);
                    list.add(num[t]);
                    ans.add(list);

                    //防止重复
                    while(j+1 < t && num[j] == num[j+1]) {
                        j ++;
                    }

                    while(t-1 > j && num[t] == num[t-1]) {
                        t --;
                    }
                    j ++;
                    t --;
                }
            }
            while(i+1 < n-2 && num[i] == num[i+1]) {
                i ++;
            }
        }
        return ans;
    }

    static class TestCase {
        public static int[] NUM = {-2,0,1,1,2};
        public static int[] NUM1 = {-10, 0, 10, 20, -10, -40};
    }
}
